package pro.softzhang.algo.lc600;

import pro.softzhang.algo.flag.knowledge.KGraph;

@KGraph
public class LC684_RedundantConnection {
    public static void main(String[] args) {

    }

    static class Solution {
        public int[] findRedundantConnection(int[][] edges) {
            int maxVertex = 0;
            for (int[] edge : edges) {
                maxVertex = Math.max(maxVertex, edge[0]);
                maxVertex = Math.max(maxVertex, edge[1]);
            }

            int[] fathers = new int[maxVertex + 1];
            for (int i = 1; i <= maxVertex; i++) {
                fathers[i] = i;
            }

            for (int[] edge : edges) {
                if (!union(fathers, edge[0], edge[1])) {
                    return edge;
                }
            }
            return new int[2];
        }

        private boolean union(int[] fathers, int i, int j) {
            int fatherOfJ = findFather(fathers, i);
            int fatherOfI = findFather(fathers, j);
            if (fatherOfI != fatherOfJ) {
                fathers[fatherOfI] = fatherOfJ;
                return true;
            }
            return false;
        }

        private int findFather(int[] fathers, int i) {
            if (fathers[i] != i) {
                fathers[i] = findFather(fathers, fathers[i]);
            }
            return fathers[i];
        }
    }
}
